/**
 * 题目Id：125
 * 题目：验证回文串
 * 日期：2023-02-28 16:07:14
 */
//如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。 
//
// 字母和数字都属于字母数字字符。 
//
// 给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。 
//
// 
//
// 示例 1： 
//
// 
//输入: s = "A man, a plan, a canal: Panama"
//输出：true
//解释："amanaplanacanalpanama" 是回文串。
// 
//
// 示例 2： 
//
// 
//输入：s = "race a car"
//输出：false
//解释："raceacar" 不是回文串。
// 
//
// 示例 3： 
//
// 
//输入：s = " "
//输出：true
//解释：在移除非字母数字字符之后，s 是一个空字符串 "" 。
//由于空字符串正着反着读都一样，所以是回文串。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 2 * 10⁵ 
// s 仅由可打印的 ASCII 字符组成 
// 
//
// Related Topics 双指针 字符串 👍 617 👎 0

package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class ValidPalindrome {
    public static void main(String[] args) {
        Solution solution = new ValidPalindrome().new Solution();
//        int[] ints = solution.twoSum(new int[]{2, 7, 11, 15}, 9);
//        int len = solution.minSubArrayLen(11, new int[]{1, 2, 3, 4, 5});
        String s = solution.reverseWords("Let's take LeetCode contest");
//        int len = solution.strStr("abcdefsdascweuicnflashcayqiwueoiqriuaspodashdlashcnz,xcbmncbakjadhqpduzhjchjdhakjdhkjcz,c,mzaqwsxdftryiop,ccmcnbcb", "fsdascweuicnflaa");

        System.out.println(s);
        System.out.println("Hello world");
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     *
     */
    class Solution {
        public boolean isPalindrome(String s) {
//        /**
//         * 1,使用list判断 移出所有的非字母字符
//         * 2，转换成小写
//         * 3，循环判断
//         */
//        List list=new ArrayList();
//        for (int i = 0; i <s.length(); i++) {
//            char c=s.charAt(i);
//            if((c>=48&&c<=57)||(c>=97&&c<=122)){
//                list.add(c);
//
//            }
//            else if(c>=65&&c<=90){
//                list.add((char)(c+32));
//            }
//
//        }
//        int left=0,right=list.size()-1;
//        while(right>left){
//            if(list.get(left)!=list.get(right)){
//                return false;
//            }
//        }
//        return true;
            /**
             * 直接使用两个指针
             * 从两端比对
             */
            int n = s.length();
            int left = 0, right = n - 1;
            while (left < right) {
                while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
                    ++left;
                }
                while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
                    --right;
                }
                if (left < right) {
                    if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
                        return false;
                    }
                    ++left;
                    --right;
                }
            }
            return true;
        }

        /**
         * 反转字符数组
         *
         * @param s
         */
        public void reverseString(char[] s) {
            if (s == null || s.length == 0) {
                return;
            }
            int left = 0, right = s.length - 1;
            char temp;
            while (left < right) {
                temp = s[left];
                s[left] = s[right];
                s[right] = temp;
                left++;
                right--;
            }

        }

        /**
         * @param nums
         * @return
         */
        public int arrayPairSum(int[] nums) {
            Arrays.sort(nums);
            int sum = 0;
            for (int i = 0; i < nums.length; i++) {
                if (i % 2 == 0) {
                    sum += nums[i];
                }

            }
            return sum;
        }

        /**
         * 两数之和
         */
        public int[] twoSum(int[] numbers, int target) {
            int l = 0, r = numbers.length - 1;
            int sum = Integer.MIN_VALUE;
            while (true) {
                sum = numbers[l] + numbers[r];
                if (sum == target) {
                    break;
                }
                if (sum > target) {
                    r--;
                    continue;
                }
                l++;
            }
            return new int[]{l + 1, r + 1};
        }

        /**
         * 连续1的最大个数
         */
        public int findMaxConsecutiveOnes(int[] nums) {
            int n = 0, maxN = Integer.MIN_VALUE;
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] == 1) {
                    n++;
                } else {
                    maxN = Math.max(maxN, n);
                    n = 0;
                }

            }
            maxN = Math.max(maxN, n);
            return maxN;
        }

        /**
         * 长度最小的子数组
         */
        public int minSubArrayLen(int target, int[] nums) {
            /**
             * 思路：快慢指针
             *设置两个指针  r和l
             * 循环遍历int数组
             * 每次设置rl的起始值是当前i
             * 在内部在循环然后
             * 如果  数组越界获得sum>target就停止
             妈的时间超时
             int length = nums.length;
             int min = Integer.MAX_VALUE;
             for(int i = 0; i < length; i++){
             int sum = 0;
             for(int j = i; j < length; j++){
             sum += nums[j];
             if(sum >= target){
             min = Math.min(min, j - i + 1);
             break;
             }
             }
             }
             return min == Integer.MAX_VALUE ? 0 : min;
             */
            /**
             * 滑动窗口
             * 第一层循环定义滑动窗口的起点 截止条件是num.lenght
             * 第二层循环 逐步向前，并且计算起点和重点的和
             * 小于的话起点超前
             * 大于的话：判起点-中点的长度和min_len，同时设置和为0   借宿内层循环进入第一层循环
             *
             */
            if (Arrays.stream(nums).sum() < target) {
                return 0;
            }
            int right = 0, sum = 0, min = Integer.MAX_VALUE;
            for (int i = 0; i < nums.length; i++) {
                while (sum < target && right < nums.length) {
                    sum += nums[right];
                    right++;
                }
                if (sum >= target) {
                    min = Math.min(min, right - i);
                    sum -= nums[i];

                }
            }
            return min;

        }

        /**
         * 反转字符串中的单词 III
         * 思路：
         * 设置双指针   left和right
         * 如果left是空格  就把left添加到buffer里面，同时left++
         * 如果不是   就把就right=left   同时right++ ，指导right也是空字符    然后把字母反转
         */
        public String reverseWords(String s) {
            StringBuffer buffer = new StringBuffer();
             int left=0,right=0;

            while (right<s.length()) {
                left=right;
                if(s.charAt(left)==' '){
                    buffer.append(s.charAt(left));
                    left++;
                }
                if(s.charAt(left)!=' '){
                    right=left;
                    while(right<s.length()&&s.charAt(right)!=' '){
                        right++;
                    }
                    //反转
                    reverse(buffer,s,left,right);
                }
            }
            return buffer.toString();

        }

        /**
         * 实现strStr
         */
        public int strStr(String haystack, String needle) {
            /**
             * 方法一，朴素匹配算法
             * 建立两个指针分别纸箱两个字符串
             * 第一层循环  匹配的那个   结束条件 长的-短的
             * 每次指针指向当前要匹配的   短的指向第一个
             * 如果字符相等就匹配下一个   不相等就结束这次循环
             */
            System.out.println(System.currentTimeMillis());
            int hay, need;
            for (int i = 0; i < haystack.length() - needle.length()+1; i++) {
                hay = i;
                need = 0;
                while (true) {
                    if (haystack.charAt(hay) == needle.charAt(need)) {
                        hay++;
                        need++;
                        if(need==needle.length()){
                            return i;
                        }
                    } else {
                        break;
                    }
                }

            }
            System.out.println(System.currentTimeMillis());
            return -1;

        }

        /**
         * 字符串匹配优化一
         * @param haystack
         * @param needle
         * @return
         */

        public int strStr2(String haystack, String needle) {
return  0;

        }


    }

    private void reverse(StringBuffer buffer, String s, int left, int right) {
        for (int i = right-1; i >= left; i--) {
            buffer.append(s.charAt(i));
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

} 
